/******************************************************************************
 This is a derivative work of the data structure presented in:
 
 http://www.cmcrossroads.com/bradapp/ftp/src/libs/C++/AvlTrees.html

 whose author is Brad Appleton (http://www.bradapp.net/). 
 
 See License.txt for license information about the use of the data
 structure.

 Please, note the links above were valid when this comment was written and 
 may not be valid at the time you read it.
 ******************************************************************************/

#ifndef AVL_H
#define AVL_H

#include <stddef.h>
#include <limits>
#include <exception>
#include <list>
#include <functional>
#include <new>

#ifndef _ASSERT
#define _ASSERT(X)
#endif

namespace cnome { namespace tst_avl {
    // cmp_t is an enumeration type indicating the result of a
    // comparison.
    //     NOTE: I would place this inside the Comparable class but 
    //           when I do, g++ complains when I use cmp_t. Even
    //           when I prefix it with Comparable:: or Comparable<Char>::
    //           (If you can get this working please let me know)
    //
    enum  cmp_t {
        MIN_CMP = -1,   // less than
        EQ_CMP  = 0,    // equal to
        MAX_CMP = 1     // greater than
    };

    // Indices into a subtree array
    //     NOTE: I would place this inside the avlNode class but 
    //           when I do, g++ complains when I use dir_t. Even
    //           when I prefix it with avlNode:: or avlNode<Char, T, Pred, Alloc>::
    //           (If you can get this working please let me know)
    //
    enum  dir_t { LEFT = 0, MIDDLE = 1, RIGHT = 2};

    // Forward declarations
    template <typename Char, typename T, typename Pred, typename Alloc>
    class factoryAvlNode;

    template <typename StringT, typename T>
    struct pair_tst_avl;

    template <typename StringT, 
              typename T, 
              typename Pred = std::less<typename StringT::value_type>,
              typename Alloc = std::allocator<pair_tst_avl<StringT, T> > >
    class tst_avl;

    namespace impl {
        template <typename StringT, typename T, typename Pred, typename Alloc>
        struct tst_avl_iterator_impl;
    }

    template <typename Char, typename T, typename Pred, typename Alloc>
    class avlTree;

    // avlNode -- Class to implement an AVL Tree
    //
    template <typename Char, 
              typename T, 
              typename Pred,
              typename Alloc>
    class avlNode {

        typedef typename Alloc:: template rebind<Char>::other Alloc_Char;
        typedef typename Alloc:: template rebind<T>::other Alloc_T;
    public:

		// Creators
		static avlNode* createAvlNode(std::size_t keySize = 1)
		{
			_ASSERT(keySize >= 0);

			size_t keySz;
			if (keySize <= 1)
				keySz = sizeof(Char);
			else 
			{
#ifdef max
#undef max
#endif
				size_t lengthOfCharsLength;
				if (keySize <= std::numeric_limits<unsigned char>::max())
					lengthOfCharsLength = 1;
				else if (keySize <  std::numeric_limits<unsigned short>::max())
					lengthOfCharsLength = 2;
				else if (keySize <  std::numeric_limits<unsigned long>::max())
					lengthOfCharsLength = 4;
				else
					throw std::invalid_argument("Invalid argument value");

				keySz = lengthOfCharsLength + keySize * sizeof(Char);
			}

			avlNode* ret = new (&keySz) avlNode(keySize);

			return ret;
		}

		static avlNode* createAvlNode(const avlNode& a, std::size_t keySize = 1)
		{
			_ASSERT(keySize >= sizeof(Char));

			size_t keySz;
			if (keySize == 1)
				keySz = sizeof(Char);
			else
			{
#ifdef max
#undef max
#endif
				size_t lengthOfCharsLength;
				if (keySize <= std::numeric_limits<unsigned char>::max())
					lengthOfCharsLength = 1;
				else if (keySize <  std::numeric_limits<unsigned short>::max())
					lengthOfCharsLength = 2;
				else if (keySize <  std::numeric_limits<unsigned long>::max())
					lengthOfCharsLength = 4;
				else
					throw std::invalid_argument("Invalid argument value");

				keySz = lengthOfCharsLength + keySize * sizeof(Char);
			}

			avlNode* ret = new (&keySz) avlNode(a, keySize);

			return ret;
		}

		template <typename Iterator>
		static avlNode* createAvlNode(Iterator first, Iterator last)
		{
			size_t keySize = 0;
			for (Iterator i = first; i != last; i++)
				keySize++;
			avlNode* node = createAvlNode(keySize);
			node->setKey(first, last);

			return node;
		}

		// Get this node's data address
		T*& getData() { 
            return data;
        }

        // Get this node's key field
        Char getKey() const { 
#ifndef AVL_DEBUG
            return  *keyAddress();
#else
            Char tmp = *keyAddress();
            _ASSERT(tmp == *keyDBG);
            return tmp;
#endif
        }

        void setKey(Char val) {
            *keyAddress() = val; 

#ifdef AVL_DEBUG
            Char tmp = *keyAddress(); 
            _ASSERT(tmp == *keyDBG);
            _ASSERT(tmp == val);
#endif
        }

        // This setKey is to be used only by the appropriate constructor
        void setKey(Char* val, std::size_t keySize = 1) {
            setKeySize(keySize);
            memcpy(keyAddress(), val, keySize*sizeof(Char)); 

#ifdef AVL_DEBUG
            Char tmp = *keyAddress(); 
            _ASSERT(tmp == *keyDBG);
            _ASSERT(tmp == *val);
#endif
        }

        // This setKey is to be used only by the appropriate constructor
        template <typename Iterator>
        void setKey(Iterator first, Iterator last) {
            _ASSERT(first != last);  // This method shouldn't be called for a Key with size equal 1

            std::size_t i;
            Iterator it;
            for (i = 0, it = first; it != last; it++, i++) {
                _ASSERT(i < keySize());
                *(keyAddress()+i) = *it; 
            }

#ifdef AVL_DEBUG
            Char tmp = *keyAddress(); 
            _ASSERT(tmp == *keyDBG);
            _ASSERT(tmp == *first);
#endif
        }

        void setBal(signed char val) {
            _ASSERT(val > -3 && val < 3);

            nodeInfo = (nodeInfo & ~BALANCEMASK) | ((static_cast<unsigned char>(val & 0x80)>>5) | (val & 0x03));

#ifdef AVL_DEBUG
            balDBG = val;
#endif
        }


        // Query the balance factor, it will be a value between -1 .. 1
        // where:
        //     -1 => left subtree is taller than right subtree
        //      0 => left and right subtree are equal in height
        //      1 => right subtree is taller than left subtree
        signed char getBal(void) const { 
            signed char ret = ((static_cast<signed char>((nodeInfo & 0x04)<<5))>>5) | (nodeInfo & 0x03);

#ifdef AVL_DEBUG
            _ASSERT(balDBG == ret);
#endif

            return ret;
        }

        // Get the item at the top of the left/right subtree of this
        // item (the result may be NULL if there is no such item).
        //
        avlNode*& subtree(dir_t dir) { 
            return *(&left+dir);
        }

        avlNode*& subtree(dir_t dir) const { 
            return const_cast<avlNode*&>(*(&left+dir));
        }

        // ----- search/insert/erase
        //
        //   NOTE: These are all static functions instead of member functions
        //         because most of them need to modify the given tree root
        //         pointer. If these were instance member functions than
        //         that would correspond to having to modify the 'this'
        //         pointer, which is not allowed in C++. Most of the 
        //         functions that are static and which take an AVL tree
        //         pointer as a parameter are static for this reason.

        // Look for the given key, return NULL if not found,
        // otherwise return the item's address.
        static T* search(const Pred& pred, Char key, avlNode* root, cmp_t cmp=EQ_CMP);

        static avlNode*& find(const Pred& pred, Char key, const avlNode *& root, cmp_t cmp=EQ_CMP);

        // insert the given key, return NULL if it was inserted,
        // otherwise return the existing item with the same key.
        static avlNode*& insert(const Pred& pred, Char* key, std::size_t keySize, 
                                T *item, avlNode*& root);

        static avlNode*& insert(const Pred& pred, Char key, avlNode*& root) {
            return insert(&key, 1, 0, root);
        }

        template <typename Iterator>
        static avlNode*& 
            insert(const Pred& pred, Iterator first, Iterator last, 
                   T *item, avlNode*& root) {
            size_t keySize;
            Iterator it;
            for (keySize=0, it = first; it != last; it++)
                keySize++;
            _ASSERT(keySize);
            Alloc_Char al_c;
            Char* key = al_c.allocate(keySize); 
            int i;
            for (i = 0, it = first; it != last; i++, it++)
                key[i] = *it;

            avlNode*& ret = insert(pred, key, keySize, item, root);
            al_c.destroy(key);

            return ret;
        }

        // erase the given key from the tree. Return the corresponding
        // node, or return NULL if it was not found.
        static T* erase(const Pred& pred, Char key, avlNode*& root, cmp_t cmp=EQ_CMP);

        static T* erase(const Pred& pred, avlNode*& root);
        
        // Verification 

        // Return the height of this tree
        int height() const;

        // Verify this tree is a valid AVL tree, return TRUE if it is,
        // return FALSE otherwise
        int check(const Pred& pred) const;

        bool isNill() { return (nodeInfo&NILLMASK)==NILLMASK; }

    private:
        static const unsigned char NILLMASK        = 0x80;
        static const unsigned char PARENTMASK      = 0x60;
        static const unsigned char LEFTPARENT      = 0x40;
        static const unsigned char MIDDLEPARENT    = 0x00;
        static const unsigned char RIGHTPARENT     = 0x20;
        static const unsigned char CHARSLENGTHMASK = 0x18;
        static const unsigned char BALANCEMASK     = 0x07;
        static const unsigned char OVERLEFBAL      = 0x06;
        static const unsigned char LEFTBAL         = 0x07;
        static const unsigned char BALANCED        = 0x00;
        static const unsigned char RIGHTBAL        = 0x01;
        static const unsigned char OVERRIGHTBAL    = 0x02;
        
#ifdef AVL_DEBUG
        Char* keyDBG;
        std::size_t keySzDBG;
        signed char balDBG;
#endif

        // Data members
        unsigned char nodeInfo;

        // Pointers to subtrees and data which exist for the node
        avlNode* parent;
        avlNode* left;
        avlNode* middle;
        avlNode* right;
        T*       data;

        Char myKey;

        // Return the opposite direction of the given index
        static  dir_t opposite(dir_t dir) { 
            return dir_t(2 - int(dir));
        }

        static avlNode* shrinkNode(avlNode*& node);

        // Routines for rebalancing and rotating subtrees

        // Perform an XX rotation for the given direction 'X'.
        // Return 1 if the tree height changes due to rotation,
        // otherwise return 0.
        static int rotateOnce(avlNode * & root, dir_t dir);

        // Perform an XY rotation for the given direction 'X'
        // Return 1 if the tree height changes due to rotation,
        // otherwise return 0.
        static int rotateTwice(avlNode * & root, dir_t dir);

        // Rebalance a (sub)tree if it has become imbalanced
        static int reBalance(avlNode * & root);

        // Perform a comparison of the given key against the given
        // item using the given criteria (min, max, or equivalence
        // comparison). Returns:
        //   EQ_CMP if the keys are equivalent
        //   MIN_CMP if this key is less than the item's key
        //   MAX_CMP if this key is greater than item's key
        cmp_t compare(const Pred& pred, Char key, cmp_t cmp=EQ_CMP) const;

        signed char decBal() {
            setBal(getBal() - 1);
            return getBal();
        }

        signed char incBal() {
            setBal(getBal() + 1);
            return getBal();
        }

        static avlNode*& findEx(Pred pred, Char key, avlNode*& root, avlNode**& prtRoot, cmp_t cmp=EQ_CMP);  

        Char* keyAddress() const {
            unsigned char lengthOfCharsLength(getLengthOfCharsLength());

            return  static_cast<Char*>(
                static_cast<void*>(
                static_cast<char*>(static_cast<void*>(const_cast<Char*>(&myKey))) + lengthOfCharsLength)
                ); 
        }

        std::size_t keySize() const {
            std::size_t ret;
            unsigned char lengthOfCharsLength(getLengthOfCharsLength());
            switch (lengthOfCharsLength) {
                case 0:
                    ret = 1;
                    break;
                case 1:
                    ret = *static_cast<unsigned char*>(static_cast<void*>(const_cast<Char*>(&myKey)));
                    break;
                case 2:
                    ret = *static_cast<unsigned short*>(static_cast<void*>(const_cast<Char*>(&myKey)));
                    break;
                case 4:
                    ret = *static_cast<long*>(static_cast<void*>(const_cast<Char*>(&myKey)));
                    break;
                default:
                    _ASSERT(false);  // Invalid value for lengthOfCharsLength
                    return -1;
            }

#ifdef AVL_DEBUG
            _ASSERT(keySzDBG == ret);
#endif

            return ret;
        }

        void setKeySize(std::size_t keySize) {
            _ASSERT(keySize > 0);  

            if (keySize == 1)
                _ASSERT(getLengthOfCharsLength()==0);
            else {
                unsigned char lengthOfCharsLength(getLengthOfCharsLength());
                _ASSERT(lengthOfCharsLength > 0 && lengthOfCharsLength < 5);
                _ASSERT((keySize >> (8*(lengthOfCharsLength-1))) > 0);  // Is the lengthOfCharsLength much greater than the necessary?   
                _ASSERT((keySize >> (8*(lengthOfCharsLength-1))) <= 0xFF); // Is the lengthOfCharsLength enough to hold keySize?   

                switch (lengthOfCharsLength) {
                    case 1:
                        *static_cast<unsigned char*>(static_cast<void*>(&myKey)) = static_cast<unsigned char>(keySize);
                        break;
                    case 2:
                        *static_cast<unsigned short*>(static_cast<void*>(&myKey)) = static_cast<unsigned short>(keySize);
                        break;
                    case 4:
                        *static_cast<unsigned long*>(static_cast<void*>(&myKey)) = static_cast<unsigned long>(keySize);
                        break;
                    default:
                        _ASSERT(false);  // Invalid value for lengthOfCharsLength
                        return;
                }
            }

#ifdef AVL_DEBUG
            keySzDBG = keySize;
#endif
        }

        unsigned char getLengthOfCharsLength() const {
            return 0x1<<(((nodeInfo&CHARSLENGTHMASK)>>3)-1);
        }

        dir_t myDirInParent() {
            dir_t ret = parent->isNill()?MIDDLE:parent->left==this?LEFT:parent->middle==this?MIDDLE:parent->right==this?RIGHT:dir_t(-1);
            if (ret == -1)
                throw std::exception();

            return ret;
        }

        avlNode*& myLinkInParent() {
            _ASSERT(parent);
            return isNill()?parent:parent->subtree(myDirInParent());
        }

        static void setAvlNode(avlNode*& lval, const avlNode* rval) {
            lval = rval;
            if (lval)
                for (dir_t d = LEFT; d <= RIGHT; d = dir_t(d+1) )
                    if (lval->subtree(d))
                        lval->subtree(d)->parent = lval;
        }
        
    private:
        // Disallow direct creation, copying and assignment
        // ----- Constructors and destructors: 
        avlNode(std::size_t keySize = 1);
        avlNode(const avlNode &a);
        avlNode(const avlNode &a, std::size_t keySize);
        ~avlNode(void);
        avlNode & operator=(const avlNode &);

        // Only the 2 method bellow are valid for new and delete methods 
        // for this class
        void* operator new(size_t, size_t*);
        void  operator delete(void *, size_t*);

        // Invalid new and delete methods
        void *operator new(std::size_t) { throw std::bad_alloc("Invalid new call"); }
        void *operator new(std::size_t, const std::nothrow_t&) { throw std::bad_alloc("Invalid new call"); }
        void *operator new[](std::size_t _Count) { throw std::bad_alloc("Invalid new call"); }
        void *operator new[](std::size_t _Count, const std::nothrow_t&) { throw std::bad_alloc("Invalid new call"); }
        void *operator new[](std::size_t _Count, void* _Ptr) { throw std::bad_alloc("Invalid new call"); }
        void operator delete(void* ) { throw std::bad_alloc("Invalid delete call"); }
        void operator delete(void* , const std::nothrow_t&) { throw std::bad_alloc("Invalid delete call"); }
        void operator delete[](void*) { throw std::bad_alloc("Invalid delete call"); }
        void operator delete[](void *, void *) { throw std::bad_alloc("Invalid delete call"); }
        void operator delete[](void*, const std::nothrow_t&) { throw std::bad_alloc("Invalid delete call"); }

        template <typename, typename, typename, typename>
        friend struct impl::tst_avl_iterator_impl;
        template <typename, typename, typename, typename>
        friend class tst_avl;
    };

    template <typename Char, 
              typename T, 
              typename Pred,
              typename Alloc>
    class factoryAvlNode{
    public:

    };

    // Class avlTree is a simple container object to "house" an avlNode
    // that represents the root-node of and avlTree. Most of the member
    // functions simply delegate to the root avlNode.
    template <typename Char, 
              typename T, 
              typename Pred,
              typename Alloc>
    class avlTree {
    private:

        typedef typename Alloc:: template rebind<Char>::other Alloc_Char;
        typedef typename Alloc:: template rebind<T>::other Alloc_T;

        // Member data
        avlNode<Char, T, Pred, Alloc>* nillNode;   // The root of the tree

        template <typename, typename, typename, typename>
        friend class tst_avl;
        template <typename, typename, typename, typename>
        friend struct impl::tst_avl_iterator_impl;
        Pred  m_pred;
        Alloc m_alloc;

        avlNode<Char, T, Pred, Alloc>*& treeRoot() const { return nillNode->subtree(MIDDLE); }
    public:
        typedef const avlNode<Char, T, Pred, Alloc>* const_iterator;

        // Constructor and destructor
        avlTree() : nillNode(avlNode<Char, T, Pred, Alloc>::createAvlNode(0)) {}

        avlTree(const Pred& pred, const Alloc& al)
            : nillNode(avlNode<Char, T, Pred, Alloc>::createAvlNode(0)), 
              m_pred(pred), m_alloc(al) {}

        avlTree(const avlTree& a)
            : nillNode(a.nillNode), m_pred(a.m_pred), m_alloc(a.m_alloc) {}

        ~avlTree() { operator delete(nillNode, 0); }

        avlTree& operator=(const avlTree& a) {
            nillNode = a.nillNode;
            return *this;
        }
        // Dump the tree to the given output stream
        void dumpTree(std::ostream & os) const;

        // See if the tree is empty
        int isEmpty() const {
            return  treeRoot()->isNill();
        }

        // search, insert, erase, and check
        T* search(Char key, cmp_t cmp=EQ_CMP) {
            return  avlNode<Char, T, Pred, Alloc>::search(m_pred, key, treeRoot(), cmp);
        }

        T* insert(Char key, T * item) {
            return  avlNode<Char, T, Pred, Alloc>::insert(m_pred, key, item, treeRoot());
        }

        T* erase(Char key, cmp_t cmp=EQ_CMP) {
            return  avlNode<Char, T, Pred, Alloc>::erase(m_pred, key, treeRoot(), cmp);
        }

        int check() const {
            return  (treeRoot()) ? treeRoot()->check(m_pred) : 1;
        }

        T& operator[](Char key) {
            T* found = search(m_pred, key);
            if (found)
                return *found;
            // Not found, insert key
            Alloc_T al_t;
            typename Alloc_T::pointer tmp = al_t.allocate(1);
            al_t.construct(tmp ,T());
            return *insert(m_pred, key, tmp);
        }

        avlNode<Char, T, Pred, Alloc>* find(Char key, cmp_t cmp=EQ_CMP) const {
            return  avlNode<Char, T, Pred, Alloc>::find(m_pred, key, treeRoot(), cmp);
        }

        const_iterator end() const {
            return const_iterator(nillNode);
        }
    };
}}  // cnome::tst_avl

#include "avl_impl.h"

#endif  /* AVL_H */
